package com.mlh.dp.买卖股票的最佳时机;

/**
 * @author 缪林辉
 * @date 2024/4/22 13:10
 * @DESCRIPTION
 */
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
// 在每一天，你可以决定是否购买和/或出售股票。
// 你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
// 返回 你能获得的 最大 利润 。
public class 买卖股票的最佳时机2 {
    //这里的思路感觉不太像动态规划，但是又有一点感觉 该解法仅限该题目，没办法给后面3 4 冷冻期提供解题思路
    //通过重叠子问题的思路
    //第i天有没有比第i-1天价格高，如果价格高，dp[i] = dp[i - 1] + prices[i] - prices[i - 1]
    //即相当于第i-1天买入，第i天卖出，赚这个差价
    //并不会影响前面i-1天的最大利润
    public static int method1(int[] prices) {
        int[] dp = new int[prices.length];
        for (int i = 1; i < dp.length; i++) {
            if (prices[i] > prices[i - 1]) {
                dp[i] = dp[i - 1] + prices[i] - prices[i - 1];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[prices.length - 1];
    }
    //这里用比较纯正的dp
    public static int method2(int[] prices) {
        int[][] dp = new int[2][prices.length];
        //dp[0][i]表示第i天不持有股票
        //dp[1][i]表示第i天持有股票
        dp[1][0]=-prices[0];
        for (int i = 1; i < prices.length; i++) {
           dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]+prices[i]);
           dp[1][i]=Math.max(dp[1][i-1],dp[0][i-1]-prices[i]);
        }
        return dp[0][prices.length-1];
    }

    //优化成滚动素组
    public static int method3(int[] prices) {
        int[] dp = new int[2];
        //dp[0][i]表示第i天不持有股票
        //dp[1][i]表示第i天持有股票
        dp[1]=-prices[0];
        for (int i = 1; i < prices.length; i++) {
            int temp=dp[0];
            dp[0]=Math.max(dp[0],dp[1]+prices[i]);
            dp[1]=Math.max(dp[1],temp-prices[i]);
        }
        return dp[0];
    }

    public static int practice(int[] prices) {
        int len=prices.length;
        int[][]dp=new int[len][2];
        dp[0][0]=-prices[0];//0为持有股票
        dp[0][1]=0;//1为不持有股票
        for (int i = 1; i <len ; i++) {
            //递推公式和1的不同，要明白为什么不同  因为1的只能买一次股票，因此没有dp[i-1][1]-prices[i]这个状态，必须是第一次买-prices[i]
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[len-1][1];
    }
}
